package com.duanjw.algorithms;

import java.util.Iterator;

/**
 * 用数组实现的栈
 * @author duanjw
 */
public class ResizingArrayStack<T> implements Iterable<T> {
    private T[] datas = (T[]) new Object[1];
    private int size = 0;

    /**
     * 添加一个元素
     *
     * @param t
     */
    public void push(T t) {
        // 当数组中元素的个数等于数组长度，调整数组大小为原来的2倍
        if (size == datas.length) {
            resize(2 * size);
        }
        datas[size++] = t;
    }


    /**
     * 删除最近添加的元素
     *
     * @return
     */
    public T pop() {
        T t = datas[--size];
        datas[size] = null;
        if (size > 0 && size == datas.length / 4) {
            resize(datas.length / 2);
        }
        return t;
    }

    /**
     * 栈是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 栈中的元素数量
     *
     * @return
     */
    public int size() {
        return size;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int i = size;
            @Override
            public boolean hasNext() {
                return i > 0;
            }

            @Override
            public T next() {
                return datas[--i];
            }
        };
    }

    /**
     * 调整数组大小
     *
     * @param max
     */
    private void resize(int max) {
        T[] temp = (T[]) new Object[max];
        for (int i = 0; i < size; i++) {
            temp[i] = datas[i];
        }
        datas = temp;
    }
}
